package practice;

import java.util.*;
import java.util.stream.Collectors;

public class Day46 {
    public int jump(int[] nums) {
        int left = 0;
        int right = 0;
        int count = 0;
        if(nums.length == 1) {
            return 0;
        }
        while(left <= right) {
            int max = 0;
            count++;
            for(int i = left; i <= right; i++) {
                if(i + nums[i] >= nums.length-1) {
                    return count;
                }
                max = Math.max(max,i+nums[i]);
            }
            left = right + 1;
            right = max;
        }
        return 0;
    }
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int x : nums) {
            set.add(x);
        }
        int max = 0;
        for(int x : set) {
            int count = 1;
            if(!set.contains(x-1)) {
                int i = x;
                while(set.contains(i+1)) {
                    count++;
                    i++;
                }
            }
            max = Math.max(max,count);
        }
        return max;
    }
    public List<List<Integer>> threeSum(int[] nums) {
        //排序+双指针
        List<List<Integer>> ret = new LinkedList<>();
        Arrays.sort(nums);
        int n = nums.length;
        int k = n-1;
        while(k >= 0) {
            int target = -nums[k];
            int left = 0;
            int right = k-1;
            while(left < right) {
                int num = nums[left] + nums[right];
                if(num > target) {
                    right--;
                }else if(num < target) {
                    left++;
                }else {
                    //去重
                    while(left < right && nums[right] == nums[right-1]) {
                        right--;
                    }
                    while(left < right && nums[left] == nums[left+1]) {
                        left++;
                    }
                    List<Integer> list = new LinkedList<>();
                    list.add(nums[left]);
                    list.add(nums[right]);
                    list.add(nums[k]);
                    ret.add(list);
                    left++;
                    right--;
                }
            }
            while(k-1 >= 0 && nums[k] == nums[k-1]) {
                k--;
            }
            k--;
        }
        return ret;
    }
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode cur = head.next;
        head.next = swapPairs(cur.next);
        cur.next = head;
        return cur;
    }
    private void swap(int[] nums,int a,int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
    public int firstMissingPositive(int[] nums) {
        //不断的进行交换直接正确下标位置
        int n = nums.length;
        for(int i = 0; i < n; i++) {
            while(nums[i] > 0  && nums[i] <= n && nums[i] != nums[nums[i]-1]) {
                swap(nums,i,nums[i]-1);
            }
        }

        for(int i = 0; i < n; i++) {
            if(nums[i]-1 != i) {
                return i+1;
            }
        }
        return n+1;
    }
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode start = newHead;
        ListNode end = newHead;
        while(end != null) {
            for(int i = 0; i < k && end != null; i++) {
                end = end.next;
            }
            if(end == null) {
                return newHead.next;
            }
            ListNode prev = start.next;
            ListNode endN = end.next;
            end.next = null;
            start.next = reverse(prev);
            prev.next = endN;
            start = prev;
            end = prev;
        }
        return newHead.next;
    }

    private ListNode reverse(ListNode node) {
        ListNode newHead = new ListNode(0);
        ListNode tail = null;
        while(node != null) {
            ListNode nodeNext = node.next;
            newHead.next = node;
            node.next = tail;
            tail = node;
            node = nodeNext;
        }
        return newHead.next;
    }

    Map<Long,Integer> map = new HashMap<>();
    long sum = 0;
    int count = 0;
    public int pathSum(TreeNode root, int targetSum) {
        map.put(0L,1);
        pathSumChild(root,targetSum);
        return count;

    }
    private void pathSumChild(TreeNode root,int targetSum) {
        if(root == null) {
            return;
        }
        sum += root.val;
        count += map.getOrDefault(sum-targetSum,0);
        map.put(sum,map.getOrDefault(sum,0) + 1);
        pathSumChild(root.left,targetSum);
        pathSumChild(root.right,targetSum);
        map.put(sum,map.getOrDefault(sum,0)-1);
        sum -= root.val;
    }

    public int maxProduct(int[] nums) {
        int n = nums.length;
        //f[i]表示以i位置为结尾的最大乘积子数组
        int[] f = new int[n+1];
        //g[i]表示以i位置为结尾的最小乘积子数组
        int[] g = new int[n+1];
        f[0] = 1;
        g[0] = 1;
        int max = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++) {
            if(nums[i-1] < 0) {
                f[i] = Math.max(nums[i-1],g[i-1]*nums[i-1]);
                g[i] = Math.min(nums[i-1],f[i-1] * nums[i-1]);
            }else {
                f[i] = Math.max(nums[i-1],f[i-1] * nums[i-1]);
                g[i] = Math.min(nums[i-1],g[i-1] * nums[i-1]);
            }
            max = Math.max(f[i],max);
        }
        return max;

    }
    public String minWindow(String s, String t) {
        int m = s.length();
        int n = t.length();
        Map<Character,Integer> sMap = new HashMap<>();
        Map<Character,Integer> tMap = new HashMap<>();
        for(char ch : t.toCharArray()) {
            tMap.put(ch,tMap.getOrDefault(ch,0)+1);
        }
        int left = 0;
        int right = 0;
        int min = Integer.MAX_VALUE;
        int retL = -1;
        int retR = -1;
        int count = 0;
        while(right < m) {
            sMap.put(s.charAt(right),sMap.getOrDefault(s.charAt(right),0)+1);
            if(sMap.getOrDefault(s.charAt(right),0) <= tMap.getOrDefault(s.charAt(right),0)) {
                count++;
            }
            while(count >= n) {
                if(min > right-left+1) {
                    min = right-left+1;
                    retL = left;
                    retR = right;
                }
                sMap.put(s.charAt(left),sMap.getOrDefault(s.charAt(left),0)-1);
                if(sMap.getOrDefault(s.charAt(left),0) < tMap.getOrDefault(s.charAt(left),0)) {
                    count--;
                }
                left++;
            }
            right++;
        }
        if(retL == -1 ||  retR == -1) {
            return "";
        }
        return s.substring(retL,retR+1);
    }

    public int jump1(int[] nums) {
        int left = 0;
        int right = 0;
        int count = 0;
        int n = nums.length;
        while(right < n-1) {
            int max = 0;
            count++;
            for(int i = left; i <= right; i++) {
                max = Math.max(max,nums[i]+i);
            }
            if(max >= n-1) {
                return count;
            }
            left = right+1;
            right = max;
        }
        return 0;
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode start = new ListNode();
        start.next = head;
        ListNode end = start;
        ListNode prev = start;
        while(end != null) {
            for(int i = 0; i < k && end != null; i++) {
                end = end.next;
            }
            if(end == null) {
                return start.next;
            }
            ListNode temp = prev.next;
            ListNode endN = end.next;
            end.next = null;
            prev.next = reverse(temp);
            temp.next = endN;
            prev = temp;
            end = temp;
        }
        return start.next;
    }
    private ListNode reverse1(ListNode node) {
        ListNode cur = null;
        ListNode newHead = new ListNode(0);
        while(node != null) {
            ListNode nodeN = node.next;
            node.next = cur;
            newHead.next = node;
            cur = node;
            node = nodeN;
        }
        return newHead.next;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }
    int pos = 0;
    private TreeNode buildTreeChild(int[] preorder,int[] inorder,int s2,int e2) {

        if(s2 > e2) {
            return null;
        }
        int i = 0;
        for(i = s2; i <= e2; i++) {
            if(preorder[pos] == inorder[i]) {
                pos++;
                break;
            }
        }
        TreeNode root = new TreeNode(inorder[i]);
        root.left = buildTreeChild(preorder,inorder,s2,i-1);
        root.right = buildTreeChild(preorder,inorder,i+1,e2);
        return root;
    }

    Map<Long,Integer> map1 = new HashMap<>();
    long sum1 = 0;
    public int pathSum1(TreeNode root, int targetSum) {
        //前缀和
        map.put(0L,1);
        return pathSumChild1(root,targetSum);
    }
    private int pathSumChild1(TreeNode root,int t) {
        if(root == null) {
            return 0;
        }
        sum += root.val;
        int ret = 0;
        ret += map.getOrDefault(sum-t,0);
        map.put(sum,map.getOrDefault(sum,0)+1);
        ret += pathSumChild(root.left,t);
        ret += pathSumChild(root.right,t);
        map.put(sum,map.getOrDefault(sum,0)-1);
        sum -= root.val;
        return ret;
    }

    public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();
        int[][] dp = new int[n+1][m+1];
        for(int i = 1; i <= n; i++) {
            dp[i][0] = i;
        }
        for(int j = 1; j <= m; j++) {
            dp[0][j] = j;
        }
        word1 = " " + word1;
        word2 = " " + word2;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(word1.charAt(i) == word2.charAt(j)) {
                    dp[i][j] = dp[i-1][j-1];
                }else {
                    dp[i][j] = 1 + Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]);
                }
            }
        }
        return dp[n][m];
    }
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] ret = new int[n];
        ret[0] = 1;
        int tmp = 1;
        for(int i = 1; i < n; i++) {
            //表示除当前位置的左边的乘积和
            ret[i] = ret[i-1] * nums[i-1];
        }
        for(int i = n-2; i >= 0; i--) {
            tmp *= nums[i+1];
            ret[i] *= tmp;
        }
        return ret;
    }
<<<<<<< Updated upstream
    public String minWindow(String s, String t) {
        Map<Character,Integer> sMap = new HashMap<>();
        Map<Character,Integer> tMap = new HashMap<>();
        for(char c : t.toCharArray()) {
            tMap.put(c,tMap.getOrDefault(c,0)+1);
        }
        int retL = -1;
        int retR = -1;
        int min = Integer.MAX_VALUE;
        int sLen = s.length();
        int tLen = t.length();
        if(sLen < tLen) {
            return "";
        }
        int k = 0;
        int i = 0;
        int j = 0;
        while(i < sLen) {
            sMap.put(s.charAt(i),sMap.getOrDefault(s.charAt(i),0)+1);
            if(sMap.getOrDefault(s.charAt(i),0) <= tMap.getOrDefault(s.charAt(i),0)) {
                k++;
            }
            //写在里面避免ODEBANC这种情况
            while(k >= tLen) {
                if(min > i-j+1) {
                    retR = i;
                    retL = j;
                    min = retR-retL+1;
                }
                sMap.put(s.charAt(j),sMap.getOrDefault(s.charAt(j),0)-1);
                if(sMap.getOrDefault(s.charAt(j),0) < tMap.getOrDefault(s.charAt(j),0)) {
                    k--;
                }
                j++;
            }
            i++;
        }
        //查找不到的情况:s:ab,t:aa
        if(retL == -1 || retR == -1) {
            return "";
        }
        return s.substring(retL,retR+1);
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        List<Integer> ret = new LinkedList<>();
        int k = 0;
        //行
        int left = 0;
        //列
        int right = 0;
        int top = m-1;
        int bottom = n-1;
        while(left <= top && right <= bottom) {
            //加载第一行
            for(int i = right; i <= bottom; i++) {
                ret.add(matrix[left][i]);
            }
            //加载最后一列
            for(int i = left+1; i <= top; i++) {
                ret.add(matrix[i][bottom]);
            }
            if(left < top && right < bottom) {
                //加载最后一行
                for(int i = bottom-1; i >= right; i--) {
                    ret.add(matrix[top][i]);
                }
                //加载第一行
                for(int i = top-1; i > left; i--) {
                    ret.add(matrix[i][right]);
                }
            }

            left++;
            right++;
            top--;
            bottom--;
        }
        return ret;
    }
        List<Integer> list = new ArrayList<>();
        List<List<Integer>> ret = new ArrayList<>();
        int sum = 0;
        public List<List<Integer>> combinationSum(int[] candidates, int target) {

            dfs(candidates,target,0);
            return ret;
        }
        private void dfs(int[] candidates,int target,int start) {
            if(sum == target) {
                ret.add(new ArrayList<>(list));
                return;
            }else if(sum > target) {
                return;
            }
            for(int i = start; i < candidates.length; i++) {
                list.add(candidates[i]);
                sum += candidates[i];
                dfs(candidates,target,i);
                list.remove(list.size()-1);
                sum -= candidates[i];
            }
        }

        public boolean searchMatrix(int[][] matrix, int target) {
            //从右上角位置开始搜素，比当前位置小的话，往左移，比当前位置大的话，往右移
            int m = matrix.length;
            int n = matrix[0].length;
            int i = 0;
            int j = n-1;
            while(i < m && j >= 0) {
                if(matrix[i][j] > target) {
                    //左移
                    j--;
                }else if(matrix[i][j] < target) {
                    //下移
                    i++;
                }else {
                    return true;
                }
            }
            return false;
        }
        nt n;
        char[] arr;
        List<String> ret = new ArrayList<>();
        public List<String> generateParenthesis(int n) {
            this.n = n;
            arr = new char[n*2];
            dfs(0,0);
            return ret;
        }

        private void dfs(int left,int total) {
            if(n*2 == total) {
                ret.add(new String(arr));
                return;
            }
            if(left < n) {
                arr[total] = '(';
                dfs(left+1,total+1);
            }
            if(total-left < left) {
                arr[total] = ')';
                dfs(left,total+1);
            }
        }


}
